1. Field of the Invention
This invention relates generally to packet data transmission systems and, more particularly, to packet data transmission systems which provide a quality of service to individual or a group of flows in a router.
2. Description of the Related Art
Many applications inherently require the network to provide them with a steady stream of packets in order to work correctly. Some typical examples are those involving audio or video playback like video conferencing or video-on-demand applications. Most of these applications perform very poorly if the network does not provide them with a certain minimum amount of bandwidth on an end-to-end basis. Furthermore, several video and audio coders can vary their rate of coding based on the bandwidth that is made available to them. Thus, an a-priori knowledge of the bandwidth that the network can provide is useful for these applications to select the appropriate parameters for the coding process. If the network can provide minimum rate guarantee to a flow, then this rate can be used by the sender to appropriately deliver packets to the network so that the receiver gets a continuous stream of packets. The net result is a smooth and timely playback operation at the receiver.
There are many other applications where the provision of an end-to-end rate guarantee might be most useful. In a Virtual Private Network these rate guarantees may be used to dimension the size and number of virtual links that need to be setup. Other situations might use the rate guarantee as a means to obtaining a certain level of service from the network. For example in a World Wide Web environment a higher rate guarantee directly translates into a shorter time for downloading web pages.
Provision of service guarantees, especially rate guarantees, is becoming increasingly important in packet networks, and in particular the Internet. This is caused by both the heterogeneity of requirements from new applications, and the growing commercialization of the Internet. Support for such service guarantees requires that the network control the amount of resources that each flow or set of flows is allowed to consume. The network resources whose consumption is to be controlled, consist primarily of buffers and link bandwidth, with buffer management and scheduling being the associated mechanisms.
FIG.1 is a prior art illustration of a scenario where a flow 50 (or set of flows) between sender 20 and receiver 21 is to be guaranteed a given level of service as it crosses network 1. As they cross network 1, packets originating from sender 20 traverse links 30 to 34 and network elements, e.g., switches or routers, 11 to 14. Resources that need to be controlled in this example are the bandwidth on links 30 to 34 and the buffer space in network elements 11 to 14. This control is effected by controllers 40 to 43, where each controller is responsible for ensuring that packets from flow 50 have access to sufficient buffers and bandwidth at the corresponding network element and link, respectively. For example, controller 41 is responsible for guaranteeing to flow 50 buffers in network element 13 and bandwidth on link 33, despite the presence of interfering traffic from flows 64 and 65 which are contending for the same resources.
There is a cost associated with implementing such resource controllers. They are required to perform a number of processing steps for each packet received, in order to determine the appropriate actions to take on the packet and enforce the desired service guarantees. The cost is a function of the number and complexity of these per packet processing steps, which usually grow with the accuracy and efficiency of the service guarantees to be provided. As a result, it is desirable to identify mechanisms, that can be used to implement resource controllers at the minimum possible cost for a given level of performance in providing service guarantees. In particular, this means devising solutions that can scale with increasing link speeds.
In that context, it is important to understand the generic cost components of resource control. As mentioned earlier, there are two types of resource control mechanisms, buffer management and scheduling, which are responsible for controlling access to buffer and link bandwidth, respectively. Of the two, it turns out that packet scheduling costs are typically greater than those associated with buffer management.
This is because buffer management only involves the decision at the time of a packet arrival of whether to admit or drop it and this decision can be made based on a fixed amount of xe2x80x9cstatexe2x80x9d information. Specifically, the information used in making buffer management decision typically consists of global state information, such as the total buffer content, and flow specific state information, such as the current number of packets for the flow. There are many examples of existing buffer management mechanisms that correspond to this model. Some of the more popular ones include threshold based mechanisms [I. Cidon, R. Guxc3xa9rin, and A. Khamisy. Protective buffer management policies. IEEE/ACM Trans. Networking, 2(3):240-246, June 199], schemes such as Early Packet Discard (EPD) [A. Romanow and S. Floyd. Dynamics of TCP traffic over ATM networks. IEEE J. Sel. Areas Commun., (13(4):633-641. May 1995, J. Turner. Maintaining high throughput during overload in ATM switches. In Proceedings of INFOCOM, pages 287-295, San Francisco, Calif., April 1996], Random Early Discard (RED) [S. Floyd and V. Jacobson. Random early detection gateways for congestion avoidance. IEEE/ACM Trans. Networking, 1(4):397-413, August 1993], and Fair RED (FRED) [D. Lin and R. Morris. Dynamics of random early detection. In Proceedings of SIGCOMM, pages 127-137, Sophia Antipolis, France, September 1997].
Scheduling decisions, on the other hand, require both flow specific state information, such as when the last packet of a flow was transmitted and the rate or delay guarantee for the flow, and operations involving all the flows currently contending for access to the link. The latter is typically in the form of insertion and deletion operations in a sorted list of packets waiting for transmission. For example in the case of algorithms such as Weighted Fair Queuing (WFQ) [A. K. J. Parekh. A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks. PhD thesis, Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, Mass. 02139, February 1992. No. LIDS-TH-2089] or rate controlled Earliest Deadline First (EDF) [L. Georgiadis, R. Guxc3xa9rin, V. Peris, and K. N. Sivarajan. Efficient network QoS provisioning based on per node traffic shaping. IEEE/ACM Trans. Networking, 4(4):482-501, August 1996], the sorted list consists of maximum departure times for packets from each active flow, where the maximum departure time for a flow is computed so as to ensure specific rate and/or delay guarantees.
FIG. 2 is a prior art illustration of the operation of buffer management and scheduling mechanisms as performed by the prior art at a typical network node to control the amount of resources that can be consumed by different flows. Packets from different flows arrive on input link 35 where they are first processed by the buffer manager unit 70. This unit makes decision of whether to accept and store an incoming packet into buffer 72, based on the total number of free buffers (white space in the figure) and the current buffer occupancy of the flow to which the packet corresponds. Specifically, the figure shows packets 51, 54, and 56 from flow f1, packets 52 from flow f4, and packets 55 from flow f3, arriving to the buffer on the input link. The buffer manager unit 70 about to process incoming packet 56 from flow f1 to determine if it should be accepted in the buffer. Based on the buffer state for flow f1 shown in FIG. 2, adding packet 56 would take flow f1 above its allocated buffer space. As a result, packet 56 will be accepted into the buffer, only if flow f1 is allowed to xe2x80x9cborrowxe2x80x9d free buffers from some other flows, e.g., flow f10. Buffer management schemes differ in how aggressive they are in allowing active flows to borrow free buffers from other flows, and this corresponds to different trade-offs between potential efficiency and protection of rate guarantees.
Transmissions out of the buffer and onto output link 36 are controlled by the scheduler, which consists of a processing unit 71 and a sorted list of packet transmission times 73. The processing unit 71 computes for each queue associated with a flow fi, the latest time ti at which the packet at head of the queue for flow fi should be transmitted on the link. In the case of a WFQ-like scheduler, this time is based on the transmission time of the previous packet from flow fi and the rate guarantee for flow fi. For example, if flow fi just transmitted a packet of size Pi at time t, and has a rate guarantee of Ri, the processing unit 71 will compute the next transmission time for a packet from flow fi as ti=t+Pi/Ri. This transmission time ti is then inserted in the sorted list 73, between the times tk and t1 such that tk less than tixe2x89xa6t1. Transmission unit 74, then selects for transmission on the output link 36, the first packet from the flow fj whose transmission time is at the head of the sorted list 73. For example, the figure shows that a packet from flow f7 is about to be transmitted on output link 36, and that the previously transmitted packets were packet 81 from flow f5, packet 82 from flow f1, packet 83 from flow f4, packet 84 from flow f3, and packet 85 again from flow f1.
FIG. 2 further illustrates an important cost component of packet scheduling, namely that the size of the sorting list 73 grows with the number of flows to which service guarantees need to be provided. This can be a major impediment to scalability as speed increases. As a result, it is desirable to devise approaches that eliminate this exposure, even if at the cost of some decrease in performance guarantees or increase in the cost of other system components that are less critical for scalability purposes.
One possible direction is to lower the cost of sorting by allowing some coarsening of the information to be sorted. This is the approach of [S. Suri, G. varghese, and G. Chandranmenon. Leap forward virtual clock: A new fair queuing scheme with guaranteed delay and throughput fairness. In Proceedings of INFOCOM, page 558-566, Kobe, Japan, April 1997], which achieves a reduction from log N to log N in complexity, where N is the number of flows to be sorted. While this helps decrease sensitivity to the number of flows, the dependency on this factor remains. A possible approach that eliminates this dependency altogether is that of the Rotating Priority Queue (RPQ) proposal of [D. Wrege and J. Liebeherr. A near-optimal packet scheduler for QoS networks. In Proceedings of INFOCOM, pages 577-585, Kobe, Japan, April 1997]. In the RPQ scheme, the ordering of packet transmissions, which the sorted list provides, is now provided by keeping a fixed number of queues and rotating the priority values of each queue every T time units. Transmissions are always from the highest priority queue, and incoming packets are put in the queue whose current priority corresponds to their desired transmission time. The complexity of the sorting operation is replaced by stepping through a set of queues on transmissions, and deciding on which queue to insert a packet in on arrivals. Accurate control of packet transmissions may require a relatively large number of queues, and furthermore the RPQ scheme alone does not provide for isolation between flows, i.e., excess traffic from one flow can impact the service guarantees of another flow.
A need therefore exists for a rate guarantee method which entirely avoids the necessity for a sorting operation, and therefore eliminates dependency on the number of flows in packet transmission decisions. The implementation must meet the further requirement of minimizing overall complexity, and more importantly, being able to also ensure rate guarantees to individual flows even in the presence of excess traffic from other flows. The method""s complexity must also not significantly depend on the accuracy of the guarantees it provides, e.g., the increase in the number of queues of RPQ.
Therefore, it is an object of the present invention to provide a method for providing rate guarantees to individual flows (or set of flows) through the use of a novel buffer management scheme.
It is yet another object of the present invention to provide a method for providing rate guarantees to individual flows which entirely avoids the need for a sorting operation and therefore eliminate the dependency on the number of flows in packet transmission decisions while further minimizing overall complexity, even in the presence of excess traffic from other flows.
It is still yet another object of the present invention to provide a method for providing rate guarantees whose complexity does not significantly depend on the accuracy of the guarantees it provides, e.g., the increase in the number of queues of RPQ.
It is a further object of the present invention to provide a method for providing rate guarantees whereby a single link may be shared amongst multiple streams with link reservations in a manner that is fair, efficient and scalable.
It is another object of the present invention to provide a method for enabling routers (switches) to support differentiated services over and above regular packet forwarding.
It is a further object of the present invention to provide a method for allowing simple FIFO scheduling of streams merged into a single class.
It is yet another object of the present invention to implement the present method as computer readable program code contained on a computer usable medium.
Accordingly, the aforementioned objectives are achieved through the use of a novel buffer management scheme that enables rate guarantees to be provided to individual flows (or sets of flows) without requiring a sophisticated scheduler that can arbitrate between packets waiting for transmission. A flow or stream is a sequence of packets originating from an application on a source and terminating in an application on a destination. By intelligently allocating and isolating the buffer space dedicated to each flow an appropriate per-flow performance guarantee can be provided.
An individual flow may require a certain quality of service guarantee from the network. While there are many different ways in which quality of service can be guaranteed to individual flows (streams) most involve complicated scheduling policies. These policies have a complexity of O(log N) where N is the number of streams that are multiplexed at the link. The method of the present invention limits the complexity of the scheduler to a simple First In First Out (FIFO) scheduler. A FIFO scheduler has O(1) complexity and is, therefore, very simple to implement. The inherent simplicity is a driving force towards widescale use as a scheduling policy in today""s routers. Despite its simplicity, one of the main drawbacks of the FIFO scheduler is it""s inability to provide service differentiation to individual streams. A single flow that is sending traffic in excess of its negotiated profile can swamp the buffers and cause packets of conforming flows to be dropped. We overcome this problem by shifting the burden of service differentiation from the scheduler to the buffer management module, which intelligently decides which packets are to be accepted to be queued up for transmission. This selective admission is used to ensure that different streams can be provided with the required bandwidth guarantees. The present invention is primarily interested in a single quality of service parameter, namely the provision of rate guarantees to streams. In other words, it is a goal of the present invention to ensure that a particular stream can be guaranteed to receive a certain minimum bandwidth at the router through the allocation of a predetermined portion of a storage buffer to each stream. By intelligently allocating and isolating the buffer space available to each flow, appropriate per-flow performance guarantees are provided.
There are many benefits to providing rate guarantees by relying solely on buffer management. In general, buffer management operations typically require a constant number of per packet processing steps, which translates into low complexity and good scalability properties. In addition, it is worth noting that buffer management, and therefore its cost, is necessary even when a separate scheduling mechanism is used. This is because scheduling at best guarantees sufficient transmission opportunities to individual flows. However, those guarantees are of little benefit, if a flow has no packets waiting because another misbehaving flow is occupying the entire buffer space. Hence, buffer management is also needed if service guarantees are to be provided.
The foregoing and other objects, advantages, manner of operation and novel features of the present invention will be understood from the following detailed description when read in conjunction with the accompanying drawings and appended claims.